package Tree;

public class _105_ConstructBinaryTreefromPreorderandInorderTraversal {
    int [] preorder;
    int [] inorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        return addNode(0, 0, inorder.length - 1);
    }

    public TreeNode addNode(int preStart, int inStart, int inEnd) {
        if (preStart > preorder.length || inStart > inEnd) {
            return null;
        }
        TreeNode newNode = new TreeNode(preorder[preStart]);
        int inPos = 0;
        for (int i = inStart; i <=inEnd ; i++) {
            if (inorder[i] == preorder[preStart]) {
                inPos = i;
            }
        }
        newNode.left = addNode(preStart + 1, inStart, inPos - 1);
        newNode.right = addNode(preStart + inPos - inStart + 1, inPos + 1, inEnd);
        return newNode;
    }
}
